Codeforces Round #520 (Div. 2)（A-E）

感觉数学题略多.

F 题解太长了..告辞..

A. Minimizing the String

水签到。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[0] = 0, a[n+1] = 1001;
    int cnt = 1, ans = 0;
    for (int i = 1; i <= n+1; i++) {
        if (a[i] == a[i-1]+1) cnt++;
        else ans = max(ans, cnt-2), cnt = 1;
    }
    ans = max(ans, cnt-2);
    cout << ans << endl;
}

B. Math

题意

给你一个数字 n，两个操作：乘上任意一个数；开根号（要求是平方数）

问最小能得到的数字是多少，至少几次操作

分析

先上唯一分解定理，最小能得到的数字一定是 n 的所有质因子乘积。

最小次数可按每个质因子分开讨论，因为开根号即为质因子个数除以 2，故先把质因子个数加成二的幂再不断除。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
bool notp[N];
int prime[N], pnum;
void sieve() {
	memset(notp, 0, sizeof(notp));
	notp[0] = notp[1] = 1;
	pnum = 0;
	for (int i = 2; i < N; i++) {
		if (notp[i] == 0) prime[++pnum] = i;
		for (int j = 1; j <= pnum && prime[j] * i < N; j++) {
			notp[prime[j] * i] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
int n;
int main() {
    sieve();
    scanf("%d", &n);
    int m = n;
    bool f = 0;
    int ans1 = 1, ans2 = 0, tmp = 0;
    for (int i = 1; i <= pnum; i++) {
        if (m % prime[i] == 0) {
            int cnt = 0;
            while (m%prime[i] == 0) cnt++, m /= prime[i];
            ans1 *= prime[i];
            if (tmp && cnt != tmp) f = 1;
            tmp = max(tmp, cnt);
        }
    }
    if (ans1 == n) {
        printf("%d 0\n", ans1);
    } else {
        int x = 1;
        while (x < tmp) x *= 2, ans2++;
        if (f || x != tmp) ans2++;
        printf("%d %d\n", ans1, ans2);
    }
}

C. Banh-mi

题意

先给你一个01串，有 q 个区间询问

操作是先在区间内选一个位置，然后把它吃掉，得到那个位置的得分，并且区间内剩余位置的得分全部加上那个位置的得分

每次询问问该区间所能得到的最大的分是多少

分析

先吃大的再吃小的最优，由于只有 0 和 1 ，就先吃 1 再吃 0

每个位置对答案的贡献可单独计算，即 1011 可看作

1000：1+1+2+4 = 2^3

100：1+1+2 = 2^2

10：1+1 = 2^1

这是第一组样例，所以很明白了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const int MOD = 1e9+7;
ll pw2[N];
int n, q, sum[N];
char s[N];
int main() {
    scanf("%d%d%s", &n, &q, s+1);
    pw2[0] = 1;
    for (int i = 1; i <= n; i++) pw2[i] = pw2[i-1]*2%MOD;
    for (int i = 1; i <= n; i++) pw2[i] = (pw2[i] + pw2[i-1]) % MOD;
    for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + s[i]-'0';
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int a = r-l+1, b = sum[r]-sum[l-1];
        ll ans = pw2[a-1];
        if (a > b) ans = (ans + MOD - pw2[a-b-1]) % MOD;
        printf("%lld\n", ans);
    }
}

D. Fun with Integers

题意

绝对值小于 n 的数字（除了0，1，-1），让每个数字与其倍数（除去 -1）连边，边权是两者之商的绝对值，问每条边限走一遍能得到的最大权值和是多少

分析

由于每个点度数都是偶数，故存在欧拉回路。所以每个连通分量里的每条边都能访问到。

实际上根据题解的证明（图中每条边都在同一个连通分量内）可以写出这样复杂度$O(\sqrt{n})$的代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int f[N];
ll sum[N];
int sf(int x) {
    return x == f[x] ? x : f[x] = sf(f[x]);
}
int n;
int main() {
    for (int i = 0; i < N; i++) f[i] = i;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        for (int j = i+i; j <= n; j += i) {
            f[sf(i)] = sf(j);
            sum[i] += 4*(j/i);
        }
    }
    for (int i = 1; i <= n; i++)
        if (sf(i) != i) sum[sf(i)] += sum[i];
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, sum[sf(i)]);
    printf("%lld\n", ans);
}

E. Company

题意

给定一棵有根树，q 个区间询问。

对于每个询问，要求区间内删去一个点后剩余点的 LCA 的深度，问删哪个点，深度最大多少

分析

没记错的话去年多校训练碰到过类似题目。

先对每个点求 DFS 序，由于所有点的 LCA 的 DFS 序的作用域一定是恰好包含所有点的 DFS 序，即这些点的 LCA 即为 DFS 序最小的和最大的两个点的 LCA 。

故删掉的一定是 DFS 序最小的点或者最大的点。

倍增求 LCA + ST 表，复杂度$O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
#define pw(i) (1<<(i))
const int N = 1e5+5;
const int LEV = 20;
vector<int> G[N];
int dph[N], fa[N][LEV];
int L[N], dfs_clock, F[N]; // dfs序和逆映射
void dfs(int rt, int f) {
    L[rt] = ++dfs_clock;
    F[dfs_clock] = rt;
    for (int i = 1; i < LEV; i++) {
        if (dph[rt]-1 < pw(i)) break;
        fa[rt][i] = fa[fa[rt][i-1]][i-1];
    }
    for (int v : G[rt]) {
        dph[v] = dph[rt]+1;
        fa[v][0] = rt;
        dfs(v, rt);
    }
}
int lca(int a, int b) {
    if (dph[a] < dph[b]) swap(a, b);
    int t = dph[a]-dph[b];
    for (int i = 0; i < LEV; i++) if (pw(i)&t) a = fa[a][i];
    for (int i = LEV-1; i >= 0; i--)
        if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    if (a != b) return fa[a][0];
    return a;
}
void init(int n) {
    for (int i = 1; i <= n; i++) G[i].clear();
    memset(fa, 0, sizeof(fa));
    dph[1] = 1;
    dfs_clock = 0;
}
int Min[N][20], Max[N][20], lg2[N];
void Init(int a[], int n) {
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i/2]+1;
    for (int i = 1; i <= n; i++) Min[i][0] = Max[i][0] = a[i];
    for (int j = 1; j <= lg2[n]; j++)
        for (int i = 1; i+pw(j)-1 <= n; i++) {
            Min[i][j] = min(Min[i][j-1], Min[i+pw(j-1)][j-1]);
            Max[i][j] = max(Max[i][j-1], Max[i+pw(j-1)][j-1]);
        }9
}
int Qmin(int l, int r) {
    if (l > r) swap(l, r);
    int k = lg2[r-l+1];
    return min(Min[l][k], Min[r+1-pw(k)][k]);
}
int Qmax(int l, int r) {
    if (l > r) swap(l, r);
    int k = lg2[r-l+1];
    return max(Max[l][k], Max[r+1-pw(k)][k]);
}
int solve(int l, int a, int r) {
    if (a == l) return lca(F[Qmin(a+1, r)], F[Qmax(a+1, r)]);
    if (a == r) return lca(F[Qmin(l, a-1)], F[Qmax(l, a-1)]);
    int f1 = lca(F[Qmin(l, a-1)], F[Qmax(l, a-1)]);
    int f2 = lca(F[Qmin(a+1, r)], F[Qmax(a+1, r)]);
    return lca(f1, f2);
}
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    init(n);//multiLCA-init
    for (int i = 2; i <= n; i++) {
        int x; scanf("%d", &x);
        G[x].push_back(i);
    }
    dfs(1, 1);
    Init(L, n);//ST-init
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        int a = F[Qmin(l, r)], b = F[Qmax(l, r)];
        int fa = solve(l, a, r), fb = solve(l, b, r);
        if (dph[fa] > dph[fb]) printf("%d %d\n", a, dph[fa]-1);
        else printf("%d %d\n", b, dph[fb]-1);
    }
}